package com.leetcode.二叉树.广度优先;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
 * @author LZF
 *
 */
public class L199二叉树的右视图 {
	/**
	 * 还是利用队列，迭代来实现，只要判断是否已经到了这一层的最后一个就行了
	 */
	public List<Integer> rightSideView(TreeNode root) {
		List<Integer> result = new ArrayList<Integer>();
		Queue<TreeNode> que = new LinkedList<>();
		if(root != null) que.offer(root);//入队
		while(!que.isEmpty()) {
			int len = que.size();//获取这一层的节点数
			while(len > 0) {
				TreeNode node = que.poll();//出队
				if(len == 1) {//如果len为1，说明这一层就剩下最后一个节点
					result.add(node.val);
				}
				if(node.left != null) que.offer(node.left);
				if(node.right != null) que.offer(node.right);
				len--;
			}
		}
		return result;
    }
	//树的定义
	class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}
}
